// 给你一个字符串S, 一个字符串T，请在字符串S里面找出包含T所有字母的最小字符串
// S = "ADOBECODEBANC" T = "ABC" 
// 输出 "BANC"

function b(S: string, T: string): string {
  let n = S
  for (let i = 0; i < S.length; i++) {
    for (let j = i + 1; j <= S.length; j++) {
      let s = S.slice(i, j)
      if (s.length < T.length) continue
      let z = true
      for (const t of T) {
        if (s.indexOf(t) === -1) {
          z = false
          break;
        }
      }
      if (z && s.length < n.length) {
        console.log(1)
        n = s
      }
    }
  }
  return n
}

// 一、最小覆盖子串
// 滑动窗口算法的思路是这样：
// 1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
// 2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
// 3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
// 4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
function slidingWindow(S: string, T: string): string {
  const needs: {
    [key: string]: number
  } = {} // 记录 T
  const window: {
    [key: string]: number
  } = {} // 记录 窗口 内 字符出现的次数
  for (let i of T) {
    needs[i] = needs[i] ? needs[i] : 0
    needs[i]++
    window[i] = 0
  }
  // 开始滑动

  let left = 0, right = 0;
  let valid = 0;
  // 记录最小覆盖子串的起始索引及长度
  let start = 0, len = Number.MAX_VALUE;
  while (right < S.length) {
    // c 是将移入窗口的字符
    let c = S[right]
    // 右移窗口
    right++
    if (needs[c]) {
      window[c]++
      if (window[c] === needs[c]) {
        valid++
      }
    }
    while (valid == T.length) {
      if (right - left < len) {
        start = left;
        len = right - left;
      }
      // d 是将移出窗口的字符
      let d = S[left];
      // 左移窗口
      left++;
      // 进行窗口内数据的一系列更新
      if (needs[d]) {
        if (window[d] == needs[d]) {
          valid--;
        }
        window[d]--;
      }
    }
  }
  return len == Number.MAX_VALUE ?
    "" : S.substr(start, len);
}

// let z = slidingWindow('ADOBECODEBACNC', 'ABC')
// console.log(z)


// 二、字符串排列

// 给定2个字符串S1 和s2 ，判断 s2 是否包含s1 的排列
// s1 = "ab" s2 = "eidbaooo"
// 输出 true
// 包含 （"ba"）

// s1 = "ab" s2 ="eidboaoo"  
// 输出 false

//1、本题移动 left 缩小窗口的时机是窗口大小大于 t.size() 时，应为排列嘛，显然长度应该是一样的。
// 2、当发现 valid == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。
// 判断 s 中是否存在 t 的排列
function checkInclusion(T: string, S: string): boolean {
  const needs: {
    [key: string]: number
  } = {} // 记录 T
  const window: {
    [key: string]: number
  } = {} // 记录 窗口 内 字符出现的次数
  for (let i of T) {
    needs[i] = needs[i] ? needs[i] : 0
    needs[i]++
    window[i] = 0
  }
  // 开始滑动

  let left = 0, right = 0;
  let valid = 0;
  while (right < S.length) {
    // c 是将移入窗口的字符
    let c = S[right]
    // 右移窗口
    right++
    if (needs[c]) {
      window[c]++
      if (window[c] === needs[c]) {
        valid++
      }
    }
    // 判断左侧窗口是否要收缩
    while (right - left >= T.length) {
      if (valid == T.length) {
        return true;
      }

      // d 是将移出窗口的字符
      let d = S[left];
      // 左移窗口
      left++;
      // 进行窗口内数据的一系列更新
      if (needs[d]) {
        if (window[d] == needs[d]) {
          valid--;
        }
        window[d]--;
      }
    }
  }
  return false
}


// let z = checkInclusion('ABC', 'ADOBECODEBACNC')
// console.log(z)

// 三、找所有字母异位词
// 给定字符串s 和一个非空字符串p, 找到s中所有是p的字母异位次的子串，返回这些子串的其实索引
// 呵呵，这个所谓的字母异位词，不就是排列吗，搞个高端的说法就能糊弄人了吗？相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引

function findAnagrams(S: string, T: string): number[] {
  const needs: {
    [key: string]: number
  } = {} // 记录 T
  const window: {
    [key: string]: number
  } = {} // 记录 窗口 内 字符出现的次数
  for (let i of T) {
    needs[i] = needs[i] ? needs[i] : 0
    needs[i]++
    window[i] = 0
  }
  // 开始滑动

  let left = 0, right = 0;
  let valid = 0;

  const res: number[] = []
  while (right < S.length) {
    // c 是将移入窗口的字符
    let c = S[right]
    // 右移窗口
    right++
    if (needs[c]) {
      window[c]++
      if (window[c] === needs[c]) {
        valid++
      }
    }
    // 判断左侧窗口是否要收缩
    while (right - left >= T.length) {
      if (valid == T.length) {
        res.push(left)
      }

      // d 是将移出窗口的字符
      let d = S[left];
      // 左移窗口
      left++;
      // 进行窗口内数据的一系列更新
      if (needs[d]) {
        if (window[d] == needs[d]) {
          valid--;
        }
        window[d]--;
      }
    }
  }
  return res
}

// let z = findAnagrams('cbaebabacd', 'abc')
// console.log(z)


// 四、最长无重复子串
// 给定一个字符串 请找出不含字符串的最长子串的长度
// 输入 "abcabcbb"
// 输出 3
// "abc"

// 输入 "bbbbb"
// 输出 1

// 输入 "pwwkew"
// 输入 3

function lengthOfLongestSubstring(s: string): number {
  const window1: {
    [key: string]: number
  } = {}
  let left = 0, right = 0
  let res = 0
  while (right < s.length) {
    let c = s[right]
    right++
    if (window1[c]) {
      window1[c]++
    } else {
      window1[c] = 1
    }
    while (window1[c] > 1) {

      let d = s[left]
      left++
      window1[d]--
    }

    res = Math.max(res, right - left)
  }
  return res
}

// let z = lengthOfLongestSubstring('bbbbbb')

// console.log(z)
